
# List [1, 2, 3, 4, 5, 6] 一组连续的数字
# 链表 是一种分散存储的结构
# - 节点 Node
# - 链表 节点连起来
class Node:
    def __init__(self, value: int, next) -> None:
        self.value = value
        self.next = next

'''
10, 1, 2 ,3, 4, 5
'''
'''
Node1 -> Node2          Node3 -> Node4 -> None

              -> Node5 ->
'''
class LinkList:
    # 创建一个链表
    def __init__(self) -> None:
        self.head = None # 链表的表头
        self.size = 0    # 链表中元素的个数

    def print(self):
        if self.head == None:
            print("An empty link list.")
            return
        
        curr = self.head
        currPos = 0 # curr 节点在链表中的位置

        while curr != None:
            if currPos != self.size - 1:
                print(f"{curr.value} ", end = "-> ") # 11 ->
            else:
                print(f"{curr.value} -> None") # 13 -> None

            curr = curr.next
            currPos += 1
        
        print("\n")

    # 给链表添加元素
    # 在链表的 idx 位置，插入值 val。
    def addAtIndex(self, idx: int, val: int):
        if self.head == None:
            self.head = Node(value = val, next = None)
            self.size += 1
            return

        # 要先确保 idx 的位置合法
        if idx > self.size or idx < 0:
            return

        # 用 value 创建一个节点
        self.size += 1
        to_add = Node(value = val, next = None) # val -> None
        
        # 关注插入到头部的情况
        if idx == 0:
            to_add.next = self.head
            self.head = to_add
            return

        # 把节点放到正确的位置上
        prev = self.head
        # 移动 prev 的循环应该执行 idx - 1 次
        for _ in range(0, idx - 1):
            prev = prev.next
        
        # 这里，prev 就是 idx 位置的前一个位置了
        to_add.next = prev.next
        prev.next = to_add

    def addAtHead(self, val: int):
        self.addAtIndex(idx = 0, val = val)

    def addAtTail(self, val: int):
        self.addAtIndex(idx = self.size, val = val)

    # 从链表指定位置删除节点
    # 删除链表位置 idx 处的节点
    def deleteAtIndex(self, idx: int):
        # 1. 确保删除位置合法
        if idx < 0 or idx >= self.size:
            return
        if self.head == None:
            return
        
        # 2. 想办法删除位置 idx 的节点
        if idx == 0:
            # 特殊处理删除头部的情况
            toDelete = self.head
            self.head = self.head.next
            toDelete.next = None
            self.size -= 1
            return

        # 找到 idx - 1 这个位置的节点
        p = 0
        node = self.head
        while p != idx - 1:
            node = node.next
            p += 1
        
        # node 就是 idx - 1 位置上的节点
        toDelete = node.next
        node.next = toDelete.next
        toDelete.next = None
        
        self.size -= 1
        return
        
    # 修改链表特定位置的元素
    def modifyAtIndex(self, idx: int, val: int):
        # 1. 确定 idx 位置合法
        if self.head == None:
            return
        
        if idx < 0 or idx >= self.size:
            return

        # 从 self.head 开始
        # 把 curr 向后移动 idx 位置
        # curr.value = val
        pos = 0
        pNode = self.head
        while pos < self.size:
            pNode = self.head.next
        
        pNode.value = val

    # 读取链表 pos 位置的值
    def getNode(self, idx: int) -> int:
        if self.head == None:
            return -1

        curr = self.head
        i = 0
        # 把 curr 向后移动 idx 次
        while i != idx:
            curr = curr.next
            i += 1
        
        # curr 就是 pos 位置的 Node
        return curr.value

    # 11 -> 12 -> 13 -> 14 -> None
    # 14 -> 13 -> 12 -> 11 -> None
    def reverse(self):
        # currH 逆序之后的链表表头
        currH = self.head

        # 只要 head 表达的节点，不是表尾
        while self.head.next != None:
            p = self.head.next
            self.head = p.next
            p.next = currH
            currH = p
        
        # 如果从 currH 出发，它所表示的链表就是逆序的链表了
        self.head = currH
